/*
 * X3DOM JavaScript Library
 * http://www.x3dom.org
 *
 * (C)2009 Fraunhofer IGD, Darmstadt, Germany
 * Dual licensed under the MIT and GPL
 *
 * Based on code originally provided by
 * Philip Taylor: http://philip.html5.org
 */

x3dom.EarClipping = {

    getIndexes : function ( linklist )
    {
        var node = linklist.first.next;
        var plane = this.identifyPlane( node.prev.point, node.point, node.next.point );
        var i,
            points,
            point_indexes,
            x,
            y;
        points = [];
        point_indexes = [];

        for ( i = 0; i < linklist.length; i++ )
        {
            node = linklist.getNode( i );
            switch ( plane )
            {
                case "XY": { x = node.point.x; y = node.point.y; break; }
                case "XZ": { x = node.point.z; y = node.point.x; break; }
                default: { x = node.point.y; y = node.point.z; }
            }
            points.push( y );
            points.push( x );
            point_indexes.push( node.point_index );
        }
        var triangles = x3dom.EarCut.triangulate( points, null, 2 );
        triangles = triangles.map( function ( m ) {return point_indexes[ m ];} ) ;
        return triangles;
    },

    getMultiIndexes : function ( linklist )
    {
        var node = linklist.first.next;
        var plane = this.identifyPlane( node.prev.point, node.point, node.next.point );
        var data = {};
        data.indices = [];
        data.point = [];
        data.normals = [];
        data.colors = [];
        data.texCoords = [];
        var mapped = {};
        mapped.indices = [];
        mapped.point = [];
        mapped.normals = [];
        mapped.colors = [];
        mapped.texCoords = [];

        var points = [];
        var i,
            x,
            y;
        for ( i = 0; i < linklist.length; i++ )
        {
            node = linklist.getNode( i );
            switch ( plane )
            {
                case "XY": { x = node.point.x; y = node.point.y; break; }
                case "XZ": { x = node.point.z; y = node.point.x; break; }
                default: { x = node.point.y; y = node.point.z; }
            }
            points.push( y );
            points.push( x );
            mapped.indices.push( node.point_index );
            mapped.point.push( node.point );
            if ( node.normals ) {mapped.normals.push( node.normals );}
            if ( node.colors ) {mapped.colors.push( node.colors );}
            if ( node.texCoords ) {mapped.texCoords.push( node.texCoords );}
        }

        var triangles = x3dom.EarCut.triangulate( points, null, 2 );
        data.indices = triangles.map( function ( m ) {return mapped.indices[ m ];} ) ;
        data.point = triangles.map( function ( m ) {return mapped.point[ m ];} ) ;
        if ( node.normals ) {data.normals = triangles.map( function ( m ) {return mapped.normals[ m ];} ) ;}
        if ( node.colors ) {data.colors = triangles.map( function ( m ) {return mapped.colors[ m ];} ) ;}
        if ( node.texCoords ) {data.texCoords = triangles.map( function ( m ) {return mapped.texCoords[ m ];} ) ;}
        return data;
    },

    identifyPlane : function ( p1, p2, p3 )
    {
        var v1x,
            v1y,
            v1z,
            v2x,
            v2y,
            v2z,
            v3x,
            v3y,
            v3z;

        v1x = p2.x - p1.x; v1y = p2.y - p1.y; v1z = p2.z - p1.z;
        v2x = p3.x - p1.x; v2y = p3.y - p1.y; v2z = p3.z - p1.z;

        v3x = Math.abs( v1y * v2z - v1z * v2y );
        v3y = Math.abs( v1z * v2x - v1x * v2z );
        v3z = Math.abs( v1x * v2y - v1y * v2x );

        var angle = Math.max( v3x, v3y, v3z );

        if ( angle == v3x )
        {
            return "YZ";
        }
        else if ( angle == v3y )
        {
            return "XZ";
        }
        else if ( angle == v3z )
        {
            return "XY";
        }
        else
        {
            return "XZ";    // error
        }
    }
};

//TODO: adjust to directly use x3dom linked list
//      move to separate file
x3dom.EarCut = {

    triangulate : function mapEarcut ( data, holes, dim )
    {
        return earcut( data, holes, dim );

        /*
The following code is
Copyright (c) 2015, Mapbox

Permission to use, copy, modify, and/or distribute this software for any purpose
with or without fee is hereby granted, provided that the above copyright notice
and this permission notice appear in all copies.
*/

        function earcut ( data, holeIndices, dim )
        {
            dim = dim || 2;

            var hasHoles = holeIndices && holeIndices.length,
                outerLen = hasHoles ? holeIndices[ 0 ] * dim : data.length,
                //outerNode = filterPoints(linkedList(data, 0, outerLen, dim, true, clockwise)),
                //AP: remember winding order
                clockwise = windingOrder( data, 0, outerLen, dim ),
                outerNode = linkedList( data, 0, outerLen, dim, true, clockwise ),
                triangles = [];

            if ( !outerNode ) {return triangles;}

            var minX,
                minY,
                maxX,
                maxY,
                x,
                y,
                size;

            if ( hasHoles ) {outerNode = eliminateHoles( data, holeIndices, outerNode, dim );}

            // if the shape is not too simple, we'll use z-order curve hash later; calculate polygon bbox
            if ( data.length > 80 * dim )
            {
                minX = maxX = data[ 0 ];
                minY = maxY = data[ 1 ];

                for ( var i = dim; i < outerLen; i += dim )
                {
                    x = data[ i ];
                    y = data[ i + 1 ];
                    if ( x < minX ) {minX = x;}
                    if ( y < minY ) {minY = y;}
                    if ( x > maxX ) {maxX = x;}
                    if ( y > maxY ) {maxY = y;}
                }

                // minX, minY and size are later used to transform coords into integers for z-order calculation
                size = Math.max( maxX - minX, maxY - minY );
            }
            earcutLinked( outerNode, triangles, dim, minX, minY, size );
            //AP: preserve winding order
            if ( clockwise === false ) {triangles.reverse();}
            return triangles;
        }

        // calculate original winding order of a polygon ring
        // AP: separated to get original winding order
        function windingOrder ( data, start, end, dim )
        {
            var sum = 0;
            var i,
                j;
            for ( i = start, j = end - dim; i < end; i += dim )
            {
                sum += ( data[ j ] - data[ i ] ) * ( data[ i + 1 ] + data[ j + 1 ] );
                j = i;
            }
            //true for clockwise
            return sum > 0;
        }

        // create a circular doubly linked list from polygon points in the specified winding order
        // AP: oclockwise = original winding order
        function linkedList ( data, start, end, dim, clockwise, oclockwise )
        {
            var i,
                j,
                last;

            // link points into circular doubly-linked list in the specified winding order
            if ( clockwise === oclockwise )
            {
                for ( i = start; i < end; i += dim ) {last = insertNode( i, data[ i ], data[ i + 1 ], last );}
            }
            else
            {
                for ( i = end - dim; i >= start; i -= dim ) {last = insertNode( i, data[ i ], data[ i + 1 ], last );}
            }

            return last;
        }
        // eliminate colinear or duplicate points
        function filterPoints ( start, end )
        {
            if ( !start ) {return start;}
            if ( !end ) {end = start;}

            var p = start,
                again;
            do
            {
                again = false;

                if ( !p.steiner && ( equals( p, p.next ) || area( p.prev, p, p.next ) === 0 ) )
                {
                    removeNode( p );
                    p = end = p.prev;
                    if ( p === p.next ) {return null;}
                    again = true;
                }
                else
                {
                    p = p.next;
                }
            } while ( again || p !== end );

            return end;
        }

        // main ear slicing loop which triangulates a polygon (given as a linked list)
        function earcutLinked ( ear, triangles, dim, minX, minY, size, pass )
        {
            if ( !ear ) {return;}

            // interlink polygon nodes in z-order
            if ( !pass && size ) {indexCurve( ear, minX, minY, size );}

            var stop = ear,
                prev,
                next;

            // iterate through ears, slicing them one by one
            while ( ear.prev !== ear.next )
            {
                prev = ear.prev;
                next = ear.next;

                if ( size ? isEarHashed( ear, minX, minY, size ) : isEar( ear ) )
                {
                    // cut off the triangle
                    triangles.push( prev.i / dim );
                    triangles.push( ear.i / dim );
                    triangles.push( next.i / dim );

                    removeNode( ear );

                    // skipping the next vertice leads to less sliver triangles
                    ear = next.next;
                    stop = next.next;

                    continue;
                }

                ear = next;

                // if we looped through the whole remaining polygon and can't find any more ears
                if ( ear === stop )
                {
                    // try filtering points and slicing again
                    if ( !pass )
                    {
                        earcutLinked( filterPoints( ear ), triangles, dim, minX, minY, size, 1 );

                        // if this didn't work, try curing all small self-intersections locally
                    }
                    else if ( pass === 1 )
                    {
                        ear = cureLocalIntersections( ear, triangles, dim );
                        earcutLinked( ear, triangles, dim, minX, minY, size, 2 );

                        // as a last resort, try splitting the remaining polygon into two
                    }
                    else if ( pass === 2 )
                    {
                        splitEarcut( ear, triangles, dim, minX, minY, size );
                    }

                    break;
                }
            }
        }

        // check whether a polygon node forms a valid ear with adjacent nodes
        function isEar ( ear )
        {
            var a = ear.prev,
                b = ear,
                c = ear.next;

            if ( area( a, b, c ) >= 0 ) {return false;} // reflex, can't be an ear

            // now make sure we don't have other points inside the potential ear
            var p = ear.next.next;

            while ( p !== ear.prev )
            {
                if ( pointInTriangle( a.x, a.y, b.x, b.y, c.x, c.y, p.x, p.y ) &&
            area( p.prev, p, p.next ) >= 0 ) {return false;}
                p = p.next;
            }

            return true;
        }

        function isEarHashed ( ear, minX, minY, size )
        {
            var a = ear.prev,
                b = ear,
                c = ear.next;

            if ( area( a, b, c ) >= 0 ) {return false;} // reflex, can't be an ear

            // triangle bbox; min & max are calculated like this for speed
            var minTX = a.x < b.x ? ( a.x < c.x ? a.x : c.x ) : ( b.x < c.x ? b.x : c.x ),
                minTY = a.y < b.y ? ( a.y < c.y ? a.y : c.y ) : ( b.y < c.y ? b.y : c.y ),
                maxTX = a.x > b.x ? ( a.x > c.x ? a.x : c.x ) : ( b.x > c.x ? b.x : c.x ),
                maxTY = a.y > b.y ? ( a.y > c.y ? a.y : c.y ) : ( b.y > c.y ? b.y : c.y );

            // z-order range for the current triangle bbox;
            var minZ = zOrder( minTX, minTY, minX, minY, size ),
                maxZ = zOrder( maxTX, maxTY, minX, minY, size );

            // first look for points inside the triangle in increasing z-order
            var p = ear.nextZ;

            while ( p && p.z <= maxZ )
            {
                if ( p !== ear.prev && p !== ear.next &&
            pointInTriangle( a.x, a.y, b.x, b.y, c.x, c.y, p.x, p.y ) &&
            area( p.prev, p, p.next ) >= 0 ) {return false;}
                p = p.nextZ;
            }

            // then look for points in decreasing z-order
            p = ear.prevZ;

            while ( p && p.z >= minZ )
            {
                if ( p !== ear.prev && p !== ear.next &&
            pointInTriangle( a.x, a.y, b.x, b.y, c.x, c.y, p.x, p.y ) &&
            area( p.prev, p, p.next ) >= 0 ) {return false;}
                p = p.prevZ;
            }

            return true;
        }

        // go through all polygon nodes and cure small local self-intersections
        function cureLocalIntersections ( start, triangles, dim )
        {
            var p = start;
            do
            {
                var a = p.prev,
                    b = p.next.next;

                // a self-intersection where edge (v[i-1],v[i]) intersects (v[i+1],v[i+2])
                if ( intersects( a, p, p.next, b ) && locallyInside( a, b ) && locallyInside( b, a ) )
                {
                    triangles.push( a.i / dim );
                    triangles.push( p.i / dim );
                    triangles.push( b.i / dim );

                    // remove two nodes involved
                    removeNode( p );
                    removeNode( p.next );

                    p = start = b;
                }
                p = p.next;
            } while ( p !== start );

            return p;
        }

        // try splitting polygon into two and triangulate them independently
        function splitEarcut ( start, triangles, dim, minX, minY, size )
        {
            // look for a valid diagonal that divides the polygon into two
            var a = start;
            do
            {
                var b = a.next.next;
                while ( b !== a.prev )
                {
                    if ( a.i !== b.i && isValidDiagonal( a, b ) )
                    {
                        // split the polygon in two by the diagonal
                        var c = splitPolygon( a, b );

                        // filter colinear points around the cuts
                        a = filterPoints( a, a.next );
                        c = filterPoints( c, c.next );

                        // run earcut on each half
                        earcutLinked( a, triangles, dim, minX, minY, size );
                        earcutLinked( c, triangles, dim, minX, minY, size );
                        return;
                    }
                    b = b.next;
                }
                a = a.next;
            } while ( a !== start );
        }

        // link every hole into the outer loop, producing a single-ring polygon without holes
        function eliminateHoles ( data, holeIndices, outerNode, dim )
        {
            var queue = [],
                i,
                len,
                start,
                end,
                list;

            for ( i = 0, len = holeIndices.length; i < len; i++ )
            {
                start = holeIndices[ i ] * dim;
                end = i < len - 1 ? holeIndices[ i + 1 ] * dim : data.length;
                list = linkedList( data, start, end, dim, false );
                if ( list === list.next ) {list.steiner = true;}
                //list = filterPoints(list);
                //if (list)
                queue.push( getLeftmost( list ) );
            }

            queue.sort( compareX );

            // process holes from left to right
            for ( i = 0; i < queue.length; i++ )
            {
                eliminateHole( queue[ i ], outerNode );
                outerNode = filterPoints( outerNode, outerNode.next );
            }

            return outerNode;
        }

        function compareX ( a, b )
        {
            return a.x - b.x;
        }

        // find a bridge between vertices that connects hole with an outer ring and and link it
        function eliminateHole ( hole, outerNode )
        {
            outerNode = findHoleBridge( hole, outerNode );
            if ( outerNode )
            {
                var b = splitPolygon( outerNode, hole );
                filterPoints( b, b.next );
            }
        }

        // David Eberly's algorithm for finding a bridge between hole and outer polygon
        function findHoleBridge ( hole, outerNode )
        {
            var p = outerNode,
                hx = hole.x,
                hy = hole.y,
                qx = -Infinity,
                m;

            // find a segment intersected by a ray from the hole's leftmost point to the left;
            // segment's endpoint with lesser x will be potential connection point
            do
            {
                if ( hy <= p.y && hy >= p.next.y )
                {
                    var x = p.x + ( hy - p.y ) * ( p.next.x - p.x ) / ( p.next.y - p.y );
                    if ( x <= hx && x > qx )
                    {
                        qx = x;
                        m = p.x < p.next.x ? p : p.next;
                    }
                }
                p = p.next;
            } while ( p !== outerNode );

            if ( !m ) {return null;}

            // look for points inside the triangle of hole point, segment intersection and endpoint;
            // if there are no points found, we have a valid connection;
            // otherwise choose the point of the minimum angle with the ray as connection point

            var stop = m,
                tanMin = Infinity,
                tan;

            p = m.next;

            while ( p !== stop )
            {
                if ( hx >= p.x && p.x >= m.x &&
                pointInTriangle( hy < m.y ? hx : qx, hy, m.x, m.y, hy < m.y ? qx : hx, hy, p.x, p.y ) )
                {
                    tan = Math.abs( hy - p.y ) / ( hx - p.x ); // tangential

                    if ( ( tan < tanMin || ( tan === tanMin && p.x > m.x ) ) && locallyInside( p, hole ) )
                    {
                        m = p;
                        tanMin = tan;
                    }
                }

                p = p.next;
            }

            return m;
        }

        // interlink polygon nodes in z-order
        function indexCurve ( start, minX, minY, size )
        {
            var p = start;
            do
            {
                if ( p.z === null ) {p.z = zOrder( p.x, p.y, minX, minY, size );}
                p.prevZ = p.prev;
                p.nextZ = p.next;
                p = p.next;
            } while ( p !== start );

            p.prevZ.nextZ = null;
            p.prevZ = null;

            sortLinked( p );
        }

        // Simon Tatham's linked list merge sort algorithm
        // http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
        function sortLinked ( list )
        {
            var i,
                p,
                q,
                e,
                tail,
                numMerges,
                pSize,
                qSize,
                inSize = 1;

            do
            {
                p = list;
                list = null;
                tail = null;
                numMerges = 0;

                while ( p )
                {
                    numMerges++;
                    q = p;
                    pSize = 0;
                    for ( i = 0; i < inSize; i++ )
                    {
                        pSize++;
                        q = q.nextZ;
                        if ( !q ) {break;}
                    }

                    qSize = inSize;

                    while ( pSize > 0 || ( qSize > 0 && q ) )
                    {
                        if ( pSize === 0 )
                        {
                            e = q;
                            q = q.nextZ;
                            qSize--;
                        }
                        else if ( qSize === 0 || !q )
                        {
                            e = p;
                            p = p.nextZ;
                            pSize--;
                        }
                        else if ( p.z <= q.z )
                        {
                            e = p;
                            p = p.nextZ;
                            pSize--;
                        }
                        else
                        {
                            e = q;
                            q = q.nextZ;
                            qSize--;
                        }

                        if ( tail ) {tail.nextZ = e;}
                        else {list = e;}

                        e.prevZ = tail;
                        tail = e;
                    }

                    p = q;
                }

                tail.nextZ = null;
                inSize *= 2;
            } while ( numMerges > 1 );

            return list;
        }

        // z-order of a point given coords and size of the data bounding box
        function zOrder ( x, y, minX, minY, size )
        {
            // coords are transformed into non-negative 15-bit integer range
            x = 32767 * ( x - minX ) / size;
            y = 32767 * ( y - minY ) / size;

            x = ( x | ( x << 8 ) ) & 0x00FF00FF;
            x = ( x | ( x << 4 ) ) & 0x0F0F0F0F;
            x = ( x | ( x << 2 ) ) & 0x33333333;
            x = ( x | ( x << 1 ) ) & 0x55555555;

            y = ( y | ( y << 8 ) ) & 0x00FF00FF;
            y = ( y | ( y << 4 ) ) & 0x0F0F0F0F;
            y = ( y | ( y << 2 ) ) & 0x33333333;
            y = ( y | ( y << 1 ) ) & 0x55555555;

            return x | ( y << 1 );
        }

        // find the leftmost node of a polygon ring
        function getLeftmost ( start )
        {
            var p = start,
                leftmost = start;
            do
            {
                if ( p.x < leftmost.x ) {leftmost = p;}
                p = p.next;
            } while ( p !== start );

            return leftmost;
        }

        // check if a point lies within a convex triangle
        function pointInTriangle ( ax, ay, bx, by, cx, cy, px, py )
        {
            return ( cx - px ) * ( ay - py ) - ( ax - px ) * ( cy - py ) >= 0 &&
           ( ax - px ) * ( by - py ) - ( bx - px ) * ( ay - py ) >= 0 &&
           ( bx - px ) * ( cy - py ) - ( cx - px ) * ( by - py ) >= 0;
        }

        // check if a diagonal between two polygon nodes is valid (lies in polygon interior)
        function isValidDiagonal ( a, b )
        {
            return equals( a, b ) || a.next.i !== b.i && a.prev.i !== b.i && !intersectsPolygon( a, b ) &&
           locallyInside( a, b ) && locallyInside( b, a ) && middleInside( a, b );
        }

        // signed area of a triangle
        function area ( p, q, r )
        {
            return ( q.y - p.y ) * ( r.x - q.x ) - ( q.x - p.x ) * ( r.y - q.y );
        }

        // check if two points are equal
        function equals ( p1, p2 )
        {
            return p1.x === p2.x && p1.y === p2.y;
        }

        // check if two segments intersect
        function intersects ( p1, q1, p2, q2 )
        {
            return area( p1, q1, p2 ) > 0 !== area( p1, q1, q2 ) > 0 &&
           area( p2, q2, p1 ) > 0 !== area( p2, q2, q1 ) > 0;
        }

        // check if a polygon diagonal intersects any polygon segments
        function intersectsPolygon ( a, b )
        {
            var p = a;
            do
            {
                if ( p.i !== a.i && p.next.i !== a.i && p.i !== b.i && p.next.i !== b.i &&
                intersects( p, p.next, a, b ) ) {return true;}
                p = p.next;
            } while ( p !== a );

            return false;
        }

        // check if a polygon diagonal is locally inside the polygon
        function locallyInside ( a, b )
        {
            return area( a.prev, a, a.next ) < 0 ?
                area( a, b, a.next ) >= 0 && area( a, a.prev, b ) >= 0 :
                area( a, b, a.prev ) < 0 || area( a, a.next, b ) < 0;
        }

        // check if the middle point of a polygon diagonal is inside the polygon
        function middleInside ( a, b )
        {
            var p = a,
                inside = false,
                px = ( a.x + b.x ) / 2,
                py = ( a.y + b.y ) / 2;
            do
            {
                if ( ( ( p.y > py ) !== ( p.next.y > py ) ) && ( px < ( p.next.x - p.x ) * ( py - p.y ) / ( p.next.y - p.y ) + p.x ) )
                {inside = !inside;}
                p = p.next;
            } while ( p !== a );

            return inside;
        }

        // link two polygon vertices with a bridge; if the vertices belong to the same ring, it splits polygon into two;
        // if one belongs to the outer ring and another to a hole, it merges it into a single ring
        function splitPolygon ( a, b )
        {
            var a2 = new Node( a.i, a.x, a.y ),
                b2 = new Node( b.i, b.x, b.y ),
                an = a.next,
                bp = b.prev;

            a.next = b;
            b.prev = a;

            a2.next = an;
            an.prev = a2;

            b2.next = a2;
            a2.prev = b2;

            bp.next = b2;
            b2.prev = bp;

            return b2;
        }

        // create a node and optionally link it with previous one (in a circular doubly linked list)
        function insertNode ( i, x, y, last )
        {
            var p = new Node( i, x, y );

            if ( !last )
            {
                p.prev = p;
                p.next = p;
            }
            else
            {
                p.next = last.next;
                p.prev = last;
                last.next.prev = p;
                last.next = p;
            }
            return p;
        }

        function removeNode ( p )
        {
            p.next.prev = p.prev;
            p.prev.next = p.next;

            if ( p.prevZ ) {p.prevZ.nextZ = p.nextZ;}
            if ( p.nextZ ) {p.nextZ.prevZ = p.prevZ;}
        }

        function Node ( i, x, y )
        {
            // vertice index in coordinates array
            this.i = i;

            // vertex coordinates
            this.x = x;
            this.y = y;

            // previous and next vertice nodes in a polygon ring
            this.prev = null;
            this.next = null;

            // z-order curve value
            this.z = null;

            // previous and next nodes in z-order
            this.prevZ = null;
            this.nextZ = null;

            // indicates whether this is a steiner point
            this.steiner = false;
        }
    }
};
